package com.hr.leetcode.链表;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 * 两两交换链表中的节点
 */
class _24_两两交换链表中的节点 {
    /**
     * 假设链表为1->2->3->4
     */
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;   //作为head的前驱节点(pre->1->2->3->4)
        ListNode temp_pre = pre;  //写个临时变量，哑指针
        while (temp_pre.next != null && temp_pre.next.next != null) {//表示第一第二个节点不为null
            ListNode start = temp_pre.next;   //start=1,(pre->1(start)->2->3->4)
            ListNode end = temp_pre.next.next;//end=2,(pre->1(start)->2(end)->3->4)
            //下面三步类似插入功能
            temp_pre.next = end;
            start.next = end.next;
            end.next = start;
            //表示下一组的当前的start为temp_pre,也就是下一组的start的前一个节点
            temp_pre = start;
        }
        //返回头节点
        return pre.next;
    }

    public ListNode swapPairs1(ListNode head) {
        if (head==null || head.next==null){
            return head;
        }
        ListNode first=head;
        ListNode second=head.next;
        //交换
        first.next= swapPairs(second.next);
        second.next=first;
        return second;
    }
}